\begin{frame}
\frametitle{Tabled matrix grammars}

\begin{define}[TXMG \cite{sironmoney1977parallelsequential}]
$G = (G_H, G_V)$ is called TXMG for $X \in \{CS, CF, RM\}$ where
\begin{itemize}
	\item $G_H$ is like in XMG
	\item $G_V = (\bigcup_{i = 1}^{k} G_i, \mathcal{P})$ where $G_i = (N_i, T, P_i, S_i)$, $i = 1, \dots, k$ are k right-linear grammars with $P_i = P_{Ni} \cup P_{Ti}$ (nonterminal and terminal rules) and $\mathcal{P}$ is a finite set of tables. 
	\item A nonterminal table t is a subset of $\bigcup_{i = 1}^{k} P_{Ni}$
	\item A terminal table t is a subset of $\bigcup_{i = 1}^{k} P_{Ti}$
\end{itemize}
\end{define}

\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Derivation}

At first generate string $S_1 \dots S_n \in I^*$ from S as before. 
Vertical derivations are now take place in parallel, restriced by tables. We write $M_1 \underset{G_V}{\Downarrow} M_2$ iff either

\begin{columns}
\begin{column}[l]{5cm}
\[
M_1 = 
\boxed{
\begin{aligned}
\begin{matrix}
a_{11} & \dots & a_{1n} \\[-1ex]
\vdots & \vdots & \vdots \\[-1ex]
a_{(m-1)1} & \dots & a_{(m-1)n} \\[-0.5ex]
A_1 & \dots & A_n
\end{matrix}
\end{aligned}
}
\]

\end{column}
\begin{column}[r]{5cm}
\[
M_2 = 
\boxed{
\begin{aligned}
\begin{matrix}
a_{11} & \dots & a_{1n} \\[-1ex]
\vdots & \vdots & \vdots \\[-1ex]
a_{(m-1)1} & \dots & a_{(m-1)n} \\[-0.5ex]
a_{m1} & \dots & a_{mn} \\[-0.5ex]
B_1 & \dots & B_n
\end{matrix}
\end{aligned}
}
\]

\end{column}
\end{columns}

\ \\

and t is a nonterminal table of $\mathcal{P}$ with rules $A_i \rightarrow a_{mi}B_i, i = 1, \dots ,n$

\pagebreak

or

\begin{columns}
\begin{column}[l]{5cm}
\[
M_1 = 
\boxed{
\begin{aligned}
\begin{matrix}
a_{11} & \dots & a_{1n} \\[-1ex]
\vdots & \vdots & \vdots \\[-1ex]
a_{(m-1)1} & \dots & a_{(m-1)n} \\[-0.5ex]
A_1 & \dots & A_n
\end{matrix}
\end{aligned}
}
\]

\end{column}
\begin{column}[r]{5cm}
\[
M_2 = 
\boxed{
\begin{aligned}
\begin{matrix}
a_{11} & \dots & a_{1n} \\[-1ex]
\vdots & \vdots & \vdots \\[-1ex]
a_{(m-1)1} & \dots & a_{(m-1)n} \\[-0.5ex]
a_{m1} & \dots & a_{mn} \\[-0.5ex]
\end{matrix}
\end{aligned}
}
\]

\end{column}
\end{columns}

\ \\

with t is a terminal table of $\mathcal{P}$ with rules $A_i \rightarrow a_{mi}, i = 1, \dots , n$

\end{frame}

\begin{frame}
\frametitle{Tabled Matrix Languages}

\begin{define}

If G is a TCSMG (TCFMG, TRMG), then \begin{align*}
M(G) = \{m \times n \text{ arrays } (a_{ij}), i = 1, \dots m, j = 1, \dots, n \text{ and } m, n \geq 1\vert \\
S \overset{*}{\underset{G_1}{\Rightarrow}} S_1 \dots S_n \overset{*}{\underset{G_2}{\Downarrow}} (a_{ij})\}
\end{align*}

is called TCSML (TCFML, TRML). 

\end{define}

\end{frame}

\begin{frame}
\frametitle{Example}

\begin{Example}
\label{example:TRMG}
$G = (G_H, G_V)$ is a TRMG with intermediates $\{S_1, S_2\}$ where
\begin{itemize}
	\item $L(G_H) = \{S_1S_2^nS_1 \vert n \geq 1\}$
	\item $G_V$ consists of tables: 
	\begin{itemize}
		\item $t_1 = \{S_1 \rightarrow xS_1, S_2 \rightarrow .S_2\}$
		\item $t_2 = \{S_1 \rightarrow xS_1, S_2 \rightarrow .A\}$
		\item $t_3 = \{S_1 \rightarrow xS_1, A \rightarrow xB\}$
		\item $t_4 = \{S_1 \rightarrow xS_1, B \rightarrow .B\}$
		\item $t_5 = \{S_1 \rightarrow x, B \rightarrow .\}$
	\end{itemize}
\end{itemize}
\end{Example}

M(G) describes Pictures containing token H of x's with .'s in between of different size and proportion. 

\end{frame}

\begin{frame}
\frametitle{Example derivation}

\[
S
\overset{*}{\Rightarrow}
\boxed{
\begin{aligned}
\begin{matrix}
S_1 & S_2 & S_2 & S_2 & S_1 
\end{matrix}
\end{aligned}
}
\overset{t_1}{\Downarrow}
\boxed{
\begin{aligned}
\begin{matrix}
X & . & . & . & X \\[-0.5ex]
S_1 & S_2 & S_2 & S_2 & S_1 
\end{matrix}
\end{aligned}
}
\]

\[
\overset{t_2}{\Downarrow}
\boxed{
\begin{aligned}
\begin{matrix}
X & . & . & . & X \\[-0.5ex]
X & . & . & . & X \\[-0.5ex]
S_1 & A & A & A & S_1 
\end{matrix}
\end{aligned}
}
\overset{t_3}{\Downarrow}
\boxed{
\begin{aligned}
\begin{matrix}
X & . & . & . & X \\[-0.5ex]
X & . & . & . & X \\[-0.5ex]
X & X & X & X & X \\[-0.5ex]
S_1 & B & B & B & S_1 
\end{matrix}
\end{aligned}
}
\overset{t_5}{\Downarrow}
\boxed{
\begin{aligned}
\begin{matrix}
X & . & . & . & X \\[-0.5ex]
X & . & . & . & X \\[-0.5ex]
X & X & X & X & X \\[-0.5ex]
X & . & . & . & X 
\end{matrix}
\end{aligned}
}
\]

\end{frame}

\begin{frame}
\frametitle{Tabled matrix languages hierachy}

\begin{thm}
\begin{enumerate}[(i)]
	\item $TRLM \subsetneq TCFML \subsetneq TCSML$
	\item $XML \subsetneq TXML$ for X = R, CF or CS
\end{enumerate}
\end{thm}

\begin{proof}
\begin{enumerate}[(i)]
	\item Clear, due to chomsky hierarchy for string languages. 
	\item $XML \subset TXML$ is clear. The language from example~\ref{example:TRMG} cannot be generated with an RMG because with RMG's the different columns cannot be coordinated. We have the same situation for CF and CS and the horizontal languages $L_{CF} = \{S_1^nS_2S_1^n \vert n \geq 1\}$ and $L_{CS} = \{S_1^nS_2S_1^nS_2S_1^n \vert n \geq 1\}$, respectively. 
\end{enumerate}
\end{proof}

\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Closure properties}

\begin{thm}
For X = R, CF or CS, the family of TXML is closed under
\begin{enumerate}[(i)]
	\item union
	\item column catenation
	\item array and column homomorphism
\end{enumerate}
\end{thm}

\begin{proof}
\begin{enumerate}
	\item clear
	\item Create $G = (G_H, G_V)$ from $G_1 = (G_{H1}, G_{V1})$ and $G_2 = (G_{H2}, G_{V2})$ as follows: $G_H$ describes $G_{H1}$\rotatebox{90}{$\ominus$}$G_{H2}$ and for $G_V$, any nonterminal table of $G_1$ is combined with any nonterminal table of $G_2$. Tables for terminals are defines just as well. It can be shown that $M(G) = M(G_1)$\rotatebox{90}{$\ominus$}$M(G_2)$. \pagebreak
	\item see \cite{sironmoney1977parallelsequential}
\end{enumerate}
\end{proof}

\end{frame}